#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2019 crane <crane@crane-pc>
#
# Distributed under terms of the MIT license.

"""

"""


class MinPrice:
    def __init__(self):
        self.house_price = [
            [100, 77, 73],
            [41, 74, 83],
            [9, 91, 93],
            [50, 16, 31],
        ]

        self.memory = {}
        self.n = len(self.house_price)

    def min_house(self):
        # 从第0所房子开始
        return min(self.min_house_rec(0, 0), self.min_house_rec(0, 1), self.min_house_rec(0, 2))

    def min_house_rec(self, from_house_kth, color_kth):
        # 从from_house_kth 到 第n座房子的最低价格
        key = (from_house_kth, color_kth)
        price = self.memory.get(key)
        if price:
            return price

        if from_house_kth == self.n-1:
            return self.house_price[from_house_kth][color_kth]

        cur_price = self.house_price[from_house_kth][color_kth]

        if color_kth == 0:
            color1 = 1
            color2 = 2

        if color_kth == 1:
            color1 = 0
            color2 = 2

        if color_kth == 2:
            color1 = 0
            color2 = 1

        follows_min = min(self.min_house_rec(from_house_kth+1, color1), self.min_house_rec(from_house_kth+1, color2))

        price = cur_price + follows_min
        self.memory[ (from_house_kth, color_kth) ] = price

        return price

def test():
    m = MinPrice()
    p = m.min_house()
    print(p)

def main():
    print("start main")
    test()

if __name__ == "__main__":
    main()
